#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <utility>
using namespace std;

#define mm(a, n) memset(a, n, sizeof a)
#define mk(a, b) make_pair(a, b)

const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<LL, LL> PLL;
typedef pair<int, LL> PIL;

inline void quickread()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

inline char nc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read()
{
    static char c = nc();
    int x = 0, f = 1;
    for (; c > '9' || c < '0'; c = nc())
        if (c == '-')
            f = -1;
    for (; c <= '9' && c >= '0'; c = nc())
        x = (x << 3) + (x << 1) + c - 48;
    return x * f;
}

int n;

const int N = 1e6 + 10;


inline void solution()
{
    n = read();
    while (n -- ) {
        int m, q;
        LL a = 0, b = 1, c = 0;
        m = read(), q = read();
        LL sum = 1;
        for (int i = 2; i <= m; i ++ ) {
            if (i % 2) {
                c = a + 2;
            } else {
                c = b * q;
            }
            sum += c;
            a = b, b = c;
        }
        printf("%lld\n", sum);
    }    
}

int main()
{
    freopen("input.txt", "r", stdin);
    quickread();
    solution();
    return 0;
}